﻿//给定一个二进制数组 nums, 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
//
//输入：nums = [0, 1]
//输出：2
//说明：[0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
//
//输入：nums = [0, 1, 0]
//输出：2
//说明：[0, 1](或[1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。
//
//输入：nums = [0, 1, 1, 1, 1, 1, 0, 0, 0]
//输出：6
//解释：[1, 1, 1, 0, 0, 0] 是具有相同数量 0 和 1 的最长连续子数组。
//
//提示：
//	1 <= nums.length <= 10^5
//	nums[i] 不是 0 就是 1


class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> hash;
        hash[0] = -1; // 默认有⼀个前缀和为0的情况

        int sum = 0, ret = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i] == 0 ? -1 : 1; // 计算当前位置的前缀和

            if (hash.count(sum))
                ret = max(ret, i - hash[sum]);
            else
                hash[sum] = i;
        }
        return ret;
    }
};